`https://labuladong.online/algo/practice-in-action/rabinkarp/#rabin-karp-%E7%AE%97%E6%B3%95`

var rabinKarp = function (txt, pat) {
  // 位数
  const L = pat.length;

  // 进制（只考虑 ASCII 编码）
  const R = 256;

  // 取一个比较大的素数作为求模的除数
  const Q = 1658598167;

  // R^(L - 1) 的结果
  const RL = 1;
  for (let i = 1; i <= L - 1; i++) {
    // 计算过程中不断求模，避免溢出
    RL = (RL * R) % Q;
  }

  // 计算模式串的哈希值
  let patHash = 0;
  for (var i = 0; i < pat.length; i++) {
    patHash = (R * patHash + pat.charCodeAt(i)) % Q;
  }

  // 滑动窗口中子字符串的哈希值
  let windowHash = 0;

  // 滑动窗口代码框架
  let left = 0, right = 0;
  while (right < txt.length) {
    // 扩大窗口，移入字符
    windowHash = ((R * windowHash) % Q + txt.charCodeAt(right)) % Q;
    right++;

    // 当子串的长度达到要求
    if (right - left === L) {
      // 根据哈希值判断是否匹配模式串
      if (windowHash === patHash) {
        // 当前窗口中的子串哈希值等于模式串的哈希值
        // 还需进一步确认窗口子串是否真的和模式串相同，避免哈希冲突
        if (pat === txt.substring(left, right)) {
          return left;
        }
      }
      // 缩小窗口，移出字符
      windowHash = (windowHash - txt.charCodeAt(left) * RL % Q + Q) % Q;
      // 因为 windowHash - (txt[left] * RL) % Q 可能是负数
      // 所以额外再加一个 Q，保证 windowHash 不会是负数
      left++;
    }
  }

  // 没有找到模式串
  return -1;
};